package com.leetcode.partition17;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LC1610可见点的最大数目 {
    
    public static int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        //以location为原点，计算其它所有点相对于location的弧度
        int x = location.get(0), y = location.get(1), answer = 0;
        //角度转换为弧度制
        double rad = angle * Math.PI / 180;
        List<Double> radList = new ArrayList<>(points.size() << 1);
        for (List<Integer> point : points) {
            int x1 = point.get(0), y1 = point.get(1);
            //如果当前点和location重合则特殊处理
            if (x1 == x && y1 == y) {
                answer++;
                continue;
            }
            radList.add(Math.atan2(y1 - y, x1 - x));
        }
        Collections.sort(radList);
        //角度a和k*2π+a是等价的，因此再添加一层2π进去
        int max = 0, size = radList.size();
        for (int i = 0; i < size; i++) radList.add(radList.get(i) + 2 * Math.PI);
        //滑动窗口计算在rad范围内的极角
        for (int i = 0, j = 0; i < size; i++) {
            while (j < 2 * size && radList.get(j) - radList.get(i) <= rad) j++;
            max = Math.max(max, j - i);
        }
        return answer + max;
    }

    public static void main(String[] args) {
        List<List<Integer>> points = new ArrayList<>();
        points.add(Arrays.asList(2, 1));
        points.add(Arrays.asList(2, 2));
        points.add(Arrays.asList(3, 3));
        int angle = 90;
        List<Integer> location = Arrays.asList(1, 1);
        System.out.println(visiblePoints(points, angle, location));
    }
}
